package com.leetcode.partition6;

import com.leetcode.common.TreeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author `RKC`
 * @date 2021/8/21 8:24
 */
public class LC501二叉搜索树中的众数 {

    private static int maxCount;
    private static TreeNode pre = null;
    private static int count = 0;

    public static int[] findMode(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root.left == null && root.right == null) return new int[]{root.val};
        iteration(result, root);
        return result.stream().mapToInt(value -> value).toArray();
    }

    public static void main(String[] args) {
//        TreeNode root = new TreeNode(1, null, new TreeNode(2, new TreeNode(2), null));
        TreeNode root = new TreeNode(1, null, new TreeNode(2));
        System.out.println(Arrays.toString(findMode(root)));
    }

    private static void iteration(List<Integer> result, TreeNode root) {
        Stack<TreeNode> s = new Stack<>();
        TreeNode cur = root, pre = null;
        int count = 0, maxCount = 0;
        while (cur != null || !s.isEmpty()) {
            if (cur != null) {
                s.push(cur);
                cur = cur.left;
            } else {
                cur = s.pop();
                if (pre == null) count = 1;
                else if (pre.val == cur.val) count++;
                else count = 1;
                if (count == maxCount) result.add(cur.val);
                if (count > maxCount) {
                    maxCount = count;
                    result.clear();
                    result.add(cur.val);
                }
                pre = cur;
                cur = cur.right;
            }
        }
    }

    private static void inorder(List<Integer> result, TreeNode root) {
        if (root == null) return;
        inorder(result, root.left);
        if (pre == null) count = 1;
        else if (pre.val == root.val) count++;      //与前一个节点相同
        else count = 1;
        pre = root;     //pre始终指向上一个节点
        if (count == maxCount) {            //和最大值相同，正常放入
            result.add(root.val);
        }
        if (count > maxCount) {
            maxCount = count;       //更新最大频率
            result.clear();        //清空结果，重新统计
            result.add(root.val);
        }
        inorder(result, root.right);
    }
}
